import java.util.ArrayList;
class Solution1 {

    public int findPeakElement (int[] nums) {

        // int left = 0;
        // int right = nums.length-1;
        // while(left < right){
        //     int mid = (left + right) >> 1;
        //     if (nums[mid] > nums[mid+1]){
        //         right = mid;
        //     }else{
        //         left = mid+1;
        //     }

        // }
        // return right;
        for (int i = 0; i < nums.length-1; i++){
            if(i==0){//当峰值为第一个元素
                if(nums[i]>nums[i+1])
                    return i;
                continue;

            }
            if (nums[i] > nums[i+1] && nums[i]>nums[i-1]){
                return i;

            }


        }
        return nums.length-1;

    }

    public int search (int[] nums, int target) {

        if (nums == null || nums.length == 0){
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] < target){
                left = mid + 1;

            }else if(nums[mid] > target){
                right =mid - 1;


            }else{
                return mid;
            }
        }
        return -1;
    }
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0){
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;
        while(left < right){
            if (right - left == 1){
                mid = left;
                break;
            }

            if (array[left] == array[right] && array[left] == array[mid]){
                int ret = array[left];
                for (int i = left +1; i < right; i++){
                    if (ret > array[i]){
                        ret = array[i];
                    }
                }
                return ret;
            }

            mid = (left + right) >> 1;
            if (array[mid] >= array[left]){
                left = mid;
            }else{
                right = mid;
            }


        }
        return array[mid];


    }
}

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length-1;
        int j = 0;
        while (i >= 0 && j < matrix[0].length){
            int flag = matrix[i][j];
            if (flag < target){
                j++;
            }
            if (flag > target){
                i--;
            }
            if (flag == target){
                return true;
            }
        }
        return false;

    }
}
public class Test {

}
